package com.atguigu.algorithm;

import java.util.Arrays;

public class Next {
    public static void main(String[] args) {
        int[] a=next(new String("bababb"));
        System.out.println(Arrays.toString(a));
    }
    public static int[] next(String str){
        int[] ret=new int[str.length()];
        ret[0]=-1;
        if(str.length()==1){
            return ret;
        }
        ret[1]=0;
        int j=1;
        int k=ret[j];
        while(j<str.length()-1){
            if(k<0 || str.charAt(j)==str.charAt(k)){
                ret[++j]=++k;
            }else{
                k=ret[k];
            }
        }
        return ret;
    }
}
